package com.practice.heap;

import java.util.Arrays;

/**
 * Convert a min heap to BST without changing its structure and of course 
 * no extra space. (G)
 */
public class HeapToBST {
	public void heap2Bst(int[] a) {
		int N = a.length;
		Arrays.sort(a);
		int[] b = new int[N];
		
		int i = leftest(0, N);
		int j = 0;
		while (j < N) {
			b[i] = a[j];
			i = successor(i, N);
			j++;
		}
		
		for (i=0; i<N; i++) a[i] = b[i];
	}
	
	private int successor(int i, int N) {
		int next = right(i, N);
		if (next >= 0) return leftest(next, N);
		
		int parent = parent(i);
		while (parent >= 0 && 2*parent+2 == i) {
			i = parent;
			parent = parent(i);
		}
		return parent;
	}
	
	private int leftest(int i, int N) {
		while (left(i, N) >= 0) i = left(i, N);
		return i;
	}
	
	private int parent(int i) {
		return i==0? -1 : (i-1)/2;
	}
	
	private int left(int i, int N) {
		return 2*i+1 < N? 2*i+1 : -1;
	}
	
	private int right(int i, int N) {
		return 2*i+2 < N? 2*i+2 : -1;
	}
	
	// -----------------------------------------------------------------
	// BST to heap
	// -----------------------------------------------------------------
	
	public void bst2heap(int a[]) {
		int n = a.length;
		reverseArm(a, 0, n);
		for (int i = 1; i < n / 2; i += 2)
			reverseArm(a, i, n);
	}

	private void reverseArm(int a[], int from, int n) {
		int to = from;
		while (to * 2 + 2 < n)
			to = to * 2 + 2;
		while (to > from) {
			int t = a[to];
			a[to] = a[from];
			a[from] = t;

			from = from * 2 + 2;
			to = to / 2 - 1;
		}
	}
}
